似乎😮
写下这篇文章的当天似乎是个愉快的周日,舍友们似乎早早就起来了,我似乎少见地没有被键盘声喊醒,感冒发烧似乎也随着美妙周日的来到悄悄离开,这周似乎做了但又没做很多事。当然,似乎最兴奋的是这周二得到论文被accpet的消息且正好赶上评奖学金。
昨晚,师弟进行学习汇报讲到leetcode,舍友 [甜心] 也打了一场双周赛(赛后讨论了一波,可惜…甜心的代码少写了一行没过掉第三题)。转念一想 嘿,似乎感觉好久没刷题了?不如就以每日一题为小甜点,开启这美妙(shit)的周日。
打开chrome 浏览器,输入leetcode.cn,回车! 找到每日一题..卧槽?hard 题?再见……
害,还是看一下题目吧。什么?岛屿面积?似乎跟2021/11/18刷的695. 岛屿的最大面积很像啊,是不是用dfs\bfs\并查集?噢!貌似增加了一个新的条件,可以将非岛屿变成岛屿是吧,所以只用把变成岛屿后导致的一系列连锁反应考虑清楚就好了。得,思路清楚了,不如用最酷炫的并查集秀一波(其实是并查集好写…DFS要想好烦,BFS肯定又长又臭)
题目
给你一个大小为 n x n 二进制矩阵 grid 。最多 只能将一格 0 变成 1 。
返回执行此操作后,grid 中最大的岛屿面积是多少?
岛屿 由一组上、下、左、右四个方向相连的 1 形成。
示例 1:
1 | 输入: grid = [[1, 0], [0, 1]] |
示例 2:
1 | 输入: grid = [[1, 1], [1, 0]] |
示例 3:
1 | 输入: grid = [[1, 1], [1, 1]] |
提示:
n == grid.length
n == grid[i].length
1 <= n <= 500
grid[i][j]
为0
或1
题解
- 先使用并查集(并查集不会?点我)构建出整个岛屿布局(相邻的1组成的块称之为一个岛屿),在着过程中计算出每个岛屿的面积
- 再找到 0 的点,尝试合并其上下左右岛屿块,并计算面积。
- 注意,上下左右本身有可能就是连接在一起的,所以,注意去重。
1 | class Solution { |
并查集相关题目
Leetcode
- 765.情侣牵手-hard
- 200.岛屿数量-medium
- 778.水位上升的泳池中游泳-hard
- 839.相似字符串组-hard
Acwing
- 图中的环
- 修改数组